#include<iostream>

using namespace std;


struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};


class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        //为空或者只有一个节点直接返回
        if (head == nullptr || head->next == nullptr)return head;

        ListNode* prev = head;
        ListNode* cur = head->next;
        ListNode* newhead = cur;
        ListNode* preprev = nullptr;//把待交换的节点组合的前一个节点记录下来，用于后续更新链接
        while (prev && cur)
        {
            //更新节点之间的链接关系，也就是交换
            prev->next = cur->next;
            cur->next = prev;

            if (preprev)preprev->next = cur;
            preprev = prev;
            //寻找下一组等待交换的节点
            prev = prev->next;
            if (prev)cur = prev->next;
        }
        return newhead;
    }
};

class Solution2 {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)return head;//出口

        ListNode* next = swapPairs(head->next->next);//相信递归一定能够把后面所有节点完成交换
        //更改链接关系
        ListNode* newhead = head->next;//旧头的next成为新头
        head->next = next;
        newhead->next = head;
        return newhead;
    }
};

int main()
{
    return 0;
}